package com.zjj.algorithm.learning.dmsxl.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的迭代遍历
 * 使用迭代方法实现遍历，需要用到栈作为支撑
 *
 * @author zjj_admin
 * @date 2022/12/22 10:26
 */
public class Tree_02_IterativeTraversal {

    public static void main(String[] args) {


        /**
         *            node1
         *      node2
         *  node3    node4
         *          node5
         *        node6
         */
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
        node5.left = node6;

        List<Integer> res1 = preOrder(node1);
        System.out.println("res1 = " + res1);

        List<Integer> res2 = midOrder(node1);
        System.out.println("res2 = " + res2);

        List<Integer> res3 = postOrder(node1);
        System.out.println("res3 = " + res3);

    }


    /**
     * 使用迭代法实现二叉树的前序遍历
     * 实现思路：
     * 1、将根节点加入栈中，将右子节点入栈（当不为null时），然后将左子节点压栈
     * 这样可以保证出栈顺序为 中、左、右
     * 前序遍历：中、左、右，所以入栈顺序为：中、右、左
     *
     * @param root
     */
    public static List<Integer> preOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return res;
    }


    /**
     * 迭代法中序遍历
     * 遍历顺序：左、中、右，入栈顺序：左、右
     *
     * @param root
     * @return
     */
    public static List<Integer> midOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            //当当前节点不为 null 时
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                //当当前节点为 null 时
                //从栈中取出当前节点
                curr = stack.pop();
                res.add(curr.val);
                curr = curr.right;
            }
        }
        return res;
    }


    /**
     * 后序遍历
     * 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
     *
     * @param root
     * @return
     */
    public static List<Integer> postOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        Collections.reverse(res);
        return res;
    }


}
